/////////////////////////////////////////////////////////////////////////////
/// @file BiTree.hpp
/// @ingroup
///
/// File containing the implementation of basic tree data structure
///
/// @see
///
/// @if REVISION_HISTORY_INCLUDED
/// @par Edit History
/// @li [0] zhalat 1-Jul-2014 Initial revision of file.
/// @endif
///
/// @par &copy;  2014 HalSoft
/////////////////////////////////////////////////////////////////////////////
#ifndef _BITREE
#define _BITREE

//***************************************************************************
// C L A S S 'S   I N T E R F A C E
//***************************************************************************
/*
 1.  ins_left(BTNode<parBiTree> *pNode, cosnt parBiTree &data);
 2.  ins_right(BTNode<parBiTree> *pNode, const parBiTree &data);
 3.  rem_left(BTNode<parBiTree> *pNode);
 4.  rem_right(BTNode<parBiTree> *pNode);
 5.  if_child_left_null(BTNode<parBiTree> *pNode);
 6.  if_child_right_null(BTNode<parBiTree> *pNode);
 7.  load_from_file(const char* fileName);
 8.  size(void);
 9.  biroot(void);
 10. tree_high(BTNode<parBiTree> *pNode);
*/

// SYSTEM INCLUDES
#include <iostream>
#include <fstream>
#include <sstream>      //for std::istringstream
#include <algorithm>
#include <vector>
#include <cstddef>
#include <string>
#include <cmath>
#include <climits>       // std::numeric_limits

// C++ PROJECT INCLUDES
//none

//forward reference
class BiTree_TestSuite;

namespace tree {

    /*---def. Node---*/
    template <class parNode>
    class BTNode
    {
    public:
        parNode data;
        BTNode *pup;
        BTNode *pRight;
        BTNode *pLeft;
        int bt; //balance tree (Avl)

        BTNode(const parNode &d, BTNode *up = NULL, BTNode *p = NULL, BTNode *l = NULL, int ibt = INT_MIN)
        {
            this->data = d;   //invoke '=' operator
            this->pup = up;   //point its parent
            this->pRight = p;
            this->pLeft = l;
            this->bt = ibt;
        }

        virtual ~BTNode()
        {}
        //make our private data available for test
        friend class ::BiTree_TestSuite;
    };

    /*---def. Help---*/
    template <class parBiTree>
    class _pair{
        public:
        BTNode<parBiTree>* p;
        int ctr;
        _pair (BTNode<parBiTree>* _p = NULL, int _ctr = 0)
        {
            p = _p;
            ctr = _ctr;
        }
    };

    /*---def. Binary tree---*/
    template <class parBiTree>
    class BiTree
    {
    public:
        BiTree(int s = 0, BTNode<parBiTree> *r = NULL)
        {
            this->msize = s;
            this->pRoot = r;
            this->plast = NULL;
        }
        virtual ~BiTree()
        {
            //remove all nodes
            this->rem_left(NULL);
        }
        BTNode<parBiTree>* ins_left(BTNode<parBiTree> *pNode, const parBiTree &data);
        BTNode<parBiTree>* ins_right(BTNode<parBiTree> *pNode, const parBiTree &data);
        bool rem_left(BTNode<parBiTree> *pNode);
        bool rem_right(BTNode<parBiTree> *pNode);
        bool if_child_left_null(BTNode<parBiTree> *pNode);
        bool if_child_right_null(BTNode<parBiTree> *pNode);
        bool load_from_file(const char* fileName);
        int size(void);
        BTNode<parBiTree>* biroot(void);
        int tree_high(BTNode<parBiTree> *pNode);

    protected:
        BTNode<parBiTree> *plast; //here's the last put node's address
        BTNode<parBiTree> *pRoot;
        int msize;

        friend std::ostream& operator<<(std::ostream &_stream,  BiTree<parBiTree> &_bitree)
        {
            using namespace std;

            vector<_pair<parBiTree> > queue;
            _pair<parBiTree> temp;
            typedef typename vector<_pair<parBiTree> >::const_iterator const_it;

            bool bEnd = false;
            int current_depth = 0;
            int line_ctr = 0;

            for( queue.push_back( _pair<parBiTree>( _bitree.biroot(), current_depth) ); bEnd != true; line_ctr++)
            {
                temp = queue.front();
                queue.erase(queue.begin());
                if(temp.ctr > current_depth)
                {
                    current_depth = temp.ctr;
                    line_ctr = 0;
                }

                if( NULL != temp.p && NULL != temp.p->pLeft )  queue.push_back( _pair<parBiTree>(temp.p->pLeft, current_depth+1) );
                else                                           queue.push_back( _pair<parBiTree>(NULL, current_depth+1) );

                if( NULL != temp.p && NULL != temp.p->pRight ) queue.push_back( _pair<parBiTree>(temp.p->pRight,current_depth+1) );
                else                                           queue.push_back( _pair<parBiTree>(NULL, current_depth+1) );

                if( temp.p == NULL )  std::cout<<( pow( 2,current_depth )-1+line_ctr )<<": "<<"   ";
                else                  std::cout<<( pow( 2,current_depth )-1+line_ctr )<<": "<<"("<<temp.p->data<<")";

                std::cout<<" -level "<<current_depth<<std::endl;

                ////////////////////////////////////////////////////////////////////
                //  checking if in the queue are data or only rubbish (i.e NULL)  //
                ////////////////////////////////////////////////////////////////////
                bEnd = true;
                for( const_it it = queue.begin(); it != queue.end(); ++it ){
                    if( it->p != NULL ){
                        bEnd = false;
                        break;
                    }
                }
                ////////////////////////////////////////////////////////////////////
            }
            return _stream;
        }
        //make our private data available for test
        friend class ::BiTree_TestSuite;
    };

    //***************************************************************************
    // PUBLIC METHODS
    //***************************************************************************
    /** @brief:  Insert new node as a left child of pointed node.
        @see:    ins_right
        @param1: parent node. If NULL means create first node.
        @param2: data to be put in new node
        @return: pointer to the new node
    */
    template <class parBiTree>
    BTNode<parBiTree>* tree::BiTree<parBiTree>::ins_left(BTNode<parBiTree> *pNode, const parBiTree &data)
    {
        BTNode<parBiTree> *pnew_node;
        BTNode<parBiTree> **pposition;

        if( NULL == pNode )
        {
            if(this->msize > 0) return NULL;
            pposition = &this->pRoot;
        }
        else if(if_child_left_null(pNode))
        {
            pposition = &pNode->pLeft;
        }
        else return NULL;

        if( (pnew_node = new BTNode<parBiTree>(data, pNode)) == NULL )
            return NULL;
        *pposition=pnew_node;
        this->plast=pnew_node;

        this->msize++;
        return plast;
    }

    /** @brief:  Insert new node as a right child of pointed node
        @see:    ins_left
        @param1: parent node. If NULL means create first node.
        @param2: data to be putted in new node
        @return: pointer to the new node
    */
    template <class parBiTree>
    BTNode<parBiTree>* BiTree<parBiTree>::ins_right(BTNode<parBiTree> *pNode, const parBiTree &data)
    {
        BTNode<parBiTree> *pnew_node;
        BTNode<parBiTree> **pposition;

        if(NULL == pNode)
        {
            if(this->msize > 0) return NULL;
            pposition = &this->pRoot;
        }
        else if(if_child_right_null(pNode))
        {
            pposition = &pNode->pRight;
        }
        else return NULL;

        if( (pnew_node = new BTNode<parBiTree>(data, pNode)) == NULL )
            return NULL;
        *pposition=pnew_node;
        this->plast=pnew_node;

        this->msize++;
        return plast;
    }

    /** @brief:  Remove branch, starts from left child of given node.
     *           All descendants will be removed (left, right)
        @see:    rem_right
        @param1: node which to be cutted branch from. If NULL remove all branch.
        @return: true - if successful, false - if fail
    */
    template <class parBiTree>
    bool BiTree<parBiTree>::rem_left(BTNode<parBiTree> *pNode)
    {
        BTNode<parBiTree> **pposition;

        if(0 == this->msize) return false;
        if(NULL == pNode)
            pposition = &this->pRoot;
        else
            pposition = &pNode->pLeft;

        if( NULL != *pposition)
        {
            rem_left( *pposition );
            rem_right( *pposition );
            delete *pposition;
            *pposition = NULL;
            this->msize--;
        }
        else
        {
            return false;
        }
        return true;
    }

    /** @brief:  Remove branch, starts from right child of given node.
     *           All descendants will be removed (left, right)
        @see:    rem_left
        @param1: node which to be cutted branch from. If NULL remove all branch.
        @return: true - if successful, false - if fail
    */
    template <class parBiTree>
    bool BiTree<parBiTree>::rem_right(BTNode<parBiTree> *pNode)
    {
        BTNode<parBiTree> **pposition;

        if(0 == this->msize) return false;
        if(NULL == pNode)
            pposition = &this->pRoot;
        else
            pposition = &pNode->pRight;

        if( NULL != *pposition )
        {
            rem_right( *pposition );
            rem_left( *pposition );
            delete *pposition;
            *pposition = NULL;
            this->msize--;
        }
        else
        {
            return false;
        }
        return true;
    }

    /** @brief:  Check if left child of given node is NULL
        @see:    if_child_right_null
        @param1: node which left child's checked
        @return: true - if NULL, false - if not NULL
    */
    template <class parBiTree>
    bool BiTree<parBiTree>::if_child_left_null(BTNode<parBiTree> *pNode)
    {
        if (NULL == pNode->pLeft) return true;
        else return false;
    }

    /** @brief:  Check if right child of given node is NULL
        @see:    if_child_left_null
        @param1: node which left child's checked
        @return: true - if NULL, false - if not NULL
    */
    template <class parBiTree>
    bool BiTree<parBiTree>::if_child_right_null(BTNode<parBiTree> *pNode)
    {
        if (NULL == pNode->pRight) return true;
        else return false;
    }

    /** @brief: Return amount of nodes in tree
        @see: -
        @param1: -
        @return: amount of nodes
    */
    template <class parBiTree>
    int BiTree<parBiTree>::size(void)
    {
        return this->msize;
    }

    /** @brief: Return pointer which points to root of tree
        @see: -
        @return: pointer to tree's root
    */
    template <class parBiTree>
    BTNode<parBiTree>* BiTree<parBiTree>::biroot(void)
    {
        return this->pRoot;
    }

    /** @brief: Create tree on the base of given file.
     *             Tree must be empty before invoking this method.
     *  @param1: the name of the file.
        @see: -
        @return: true if ok
    */
    template <class parBiTree>
    bool BiTree<parBiTree>::load_from_file(const char* fileName)
    {
        using namespace std;
        fstream tfile;
        string _data;
        int _size,i;
        parBiTree x,y,z;
        bool bfailx,bfaily,bfailz;
        BTNode<parBiTree> *ptemp;
        vector< BTNode<parBiTree>* > queue;

        //prevent loading data to non zero tree
        if(this->size()>0) return false;

        //loading data..
        tfile.open( fileName, ios::in );
        if( !tfile.good() ) throw "error_can_not_read_file";
        tfile>>_size;

        for( i=0; !tfile.eof() && i<_size; i++ )
        {
            //read file in sequence
            bfailx=bfaily=bfailz=false;
            tfile>>x;
            if(std::ios_base::failbit & tfile.rdstate()) bfailx=true;
            tfile.clear();
            tfile>>y;
            if(std::ios_base::failbit & tfile.rdstate()) bfaily=true;
            tfile.clear();
            tfile>>z;
            if(std::ios_base::failbit & tfile.rdstate()) bfailz=true;
            tfile.clear();

            if(0==i)
                queue.push_back(ins_left(NULL, x));

            ptemp = queue.front();
            queue.erase(queue.begin());

            if( false == bfaily && static_cast<unsigned char>(y) != '-' )
                queue.push_back(ins_left(ptemp, y));
            else
                ptemp->pLeft = NULL;
            if( false == bfailz && static_cast<unsigned char>(z) != '-' )
                queue.push_back(ins_right(ptemp, z));
            else
                ptemp->pRight = NULL;
        }
        tfile.close();
        if (i!=_size) return false;
        else return true;
    }

    /** @brief: Calculate the high of tree from given node
     *     @see: -
     *  @param1: node from where high will be calculated.
     *           If NULL, return -1.
        @return: high of tree from pointed node or -1 if NULL.
    */
    template <class parBiTree>
    int BiTree<parBiTree>::tree_high(BTNode<parBiTree> *pNode)
    {
        // skip any action if NULL
        if( NULL == pNode ) return -1;

        using namespace std;

        vector<_pair<parBiTree> > queue;
        _pair<parBiTree> temp;
        typedef typename vector<_pair<parBiTree> >::const_iterator const_it;

        bool bEnd = false;
        int current_depth = 0;
        int line_ctr = 0;

        for( queue.push_back( _pair<parBiTree>( pNode, current_depth ) ); bEnd != true; line_ctr++ )
        {
            temp = queue.front();
            queue.erase( queue.begin() );
            if( temp.ctr > current_depth )
            {
                current_depth = temp.ctr;
                line_ctr = 0;
            }

            if( NULL != temp.p && NULL != temp.p->pLeft )  queue.push_back( _pair<parBiTree>(temp.p->pLeft, current_depth+1) );
            else                                           queue.push_back( _pair<parBiTree>(NULL, current_depth+1) );

            if( NULL != temp.p && NULL != temp.p->pRight ) queue.push_back( _pair<parBiTree>(temp.p->pRight,current_depth+1) );
            else                                           queue.push_back( _pair<parBiTree>(NULL, current_depth+1) );

            ////////////////////////////////////////////////////////////////////
            //  checking if in the queue are data or only rubbish (i.e NULL)  //
            ////////////////////////////////////////////////////////////////////
            bEnd = true;
            for( const_it it = queue.begin(); it != queue.end(); ++it ){
                if( it->p != NULL ){
                    bEnd = false;
                    break;
                }
            }
            ////////////////////////////////////////////////////////////////////
        }
        return current_depth;
    }
}
#endif//_BITREE
